//
// Description: 36. 有效的数独
// Created by Loading on 2021/9/17.
//

#include <bits/stdc++.h>

using namespace std;

bool isValidSudoku(vector<vector<char>> &board) {
    // 行、列、子集的哈希集合
    unordered_set<char> rows[9], cols[9], sub[3][3];
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            char c = board[i][j];
            if (c != '.') {
                if (rows[i].find(c) != rows[i].end()) {
                    return false;
                }
                if (cols[j].find(c) != cols[j].end()) {
                    return false;
                }
                if (sub[i / 3][j / 3].find(c) != sub[i / 3][j / 3].end()) {
                    return false;
                }
                rows[i].insert(c);
                cols[j].insert(c);
                sub[i / 3][j / 3].insert(c);
            }
        }
    }

    return true;
}

int main() {
    vector<vector<char>> board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                                  {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                                  {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                                  {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                                  {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                                  {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                                  {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                                  {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                                  {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

    bool res = isValidSudoku(board);
    cout << res << endl;

    return 0;
}